其實貪心只是一種思路，時常體現在各種算法裡面，像之前講的最小生成樹(prim)，最短路徑(Dijkstra)就是展現了貪心的思路。

• 最小生成樹 - prim
  ((用priority_queue(堆)實現貪心思想(利用pq來搜索路徑)
  ((取出pq最前面的元素，放入相鄰的節點))
• 最短路徑 - Disjkstra
  ((基於貪心思想，從起點找一個離起點最近的節點->這一個邊無法再鬆弛->用這一個邊去對其他邊鬆弛))

這種題目也沒有固定的做法，只是遵循這種思路再去設計貪心的策略，就整理幾題~~

例題實戰

122. 买卖股票的最佳时机 II
這題乍看下是DP，但其實貪心思路是可以求出答案的~~
原因是最佳解就只是每一段上升價差的和((掌握到最好的價差時間，也只能獲得每一段價差和))，所以是一個貪心思路，直接算整個數組上升和

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int res = 0;
        for(int i = 1; i<n; ++i){
            if(prices[i]>prices[i-1]){
                res+=prices[i]-prices[i-1];
            }
        }
        return res;
    }
};

1833. 雪糕的最大数量
沒別的..就先從便宜的開始買..

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int res = 0;
        for(int i = 0; i<costs.size(); ++i){
            if(coins>=costs[i]){
                coins-=costs[i];
                res++;
            }
        }
        return res;
    }
};

11. 盛最多水的容器
貪心思路：從兩側開始移動，比較左右邊界，如果其中一側比較矮，先移動那一側(才有可能使容量變大)

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int l = height.size()-1;
        int r = 0;
        while(r<l){
            res = max(res, (l-r)*min(height[l], height[r]));
            if(height[r]<height[l]){
                r++;
            }
            else{
                l--;
            }
        }
        return res;
    }
};

其他應用

機器學習中，Decision Trees，也是用到這種思路去選擇樹的建構~~